class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		int n = S.length();
		int m = T.length();
		vector<int> src_count(256);
		vector<int> count(256);

		for (int i = 0; i < m; ++i) {
			++src_count[T[i]];
		}

		int sum = 0;
		int cur = 0;
		int begin = -1;
		int end = -1;

		for (int i = 0; i < n; ++i) {
			if (src_count[S[i]] == 0) {
				continue;
			}
			++count[S[i]];
			if (count[S[i]] <= src_count[S[i]]) {
				++sum;
			}
			while (true) {
				if (src_count[S[cur]] == 0) {
					++cur;
					continue;
				}
				if (count[S[cur]] > src_count[S[cur]]) {
					--count[S[cur]];
					++cur;
				} else {
					break;
				}
			}
			if (sum == m) {
				if (begin < 0 || i - cur + 1 < end - begin + 1) {
					begin = cur;
					end = i;
				}
			}
		}
		if (begin < 0) {
			return "";
		} else {
			return S.substr(begin, end - begin + 1);
		}
    }
};